//2684.矩阵中移动的最大次数
//https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/?envType=daily-question&envId=2024-03-16
class Solution {
    int dx[3] = { -1,0,1 };
    int m = 0, n = 0;
public:
    int maxMoves(vector<vector<int>>& grid) {
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));
        m = grid.size(), n = grid[0].size();
        int ret = 0;
        for (int i = 0; i < m; ++i)
        {
            for (int k = 0; k < 3; ++k)
            {
                int px = i + dx[k];
                if (px<m && px >= 0 && n >= 1 && grid[px][1] > grid[i][0])
                    ret = max(ret, dfs(grid, dp, px, 1));
            }
        }
        return ret;
    }

    int dfs(vector<vector<int>>& grid, vector<vector<int>>& dp, int x, int y)
    {
        if (dp[x][y]) return dp[x][y];
        int ret = 0;
        for (int k = 0; k < 3; ++k)
        {
            int px = x + dx[k], py = y + 1;
            if (px < m && px >= 0 && py<n && grid[px][py] > grid[x][y])
            {
                dp[px][py] = dfs(grid, dp, px, py);
                ret = max(ret, dp[px][py]);
            }
        }
        dp[x][y] = max(ret + 1, dp[x][y]);
        return dp[x][y];
    }
};